SGU106 扩展欧几里得

Posted on | In ,

给出 $a, b,c$ 和 $x1, x2, y1, y2,$ 问满足 $ax+by+c=0$ 的 $x1<=x<=x2$ 和 $y1<=y<=y2$ 的对数有多少 $(a,b,c,x1,x2,y1,y<=10^{18})$

首先必须把a，b，c都处理0或正数

  • 分类讨论a，b为0的情况
  • 扩展欧几里得求出通解
  • 算出合法的对数，x，y的k取交集
  • 算区间左端点ceil，右端点floor，注意正数和负数取整不一样

Trick：想不通最后为什么a，b要除gcd(a,b)啊
我好难过.jpg

update：
考虑给$ax+by = gcd(a, b) =d$，ax项增加，bx减少，但和不变，这一项最小就是 $lcm(a,b)$

通解：
$$
x=x_0+k·b/\gcd(a,b)
$$
$$
y=y_0-k·a/\gcd(a,b)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll maxn = 1e6+7;

ll a, b, c, x1, x2, y1, y2;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    ll d=a;
    if(b!=0){ d=exgcd(b,a%b,y,x); y-=(a/b)*x; }
    else{ x=1; y=0; }
    return d;
}

 // 向上、向下取整(正负数)
 ll floor(ll x, ll y) {  if(x >= 0) return x / y; return (x - y + 1) / y; }
 ll ceil (ll x, ll y) {  if(x >= 0) return (x + y - 1) / y;  return x / y; }

int main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld", &a, &b, &c, &x1, &x2, &y1, &y2);
    c=-c;
    if(a<0){
        a=-a; x1=-x1; x2=-x2; swap(x1, x2);
    }
    if(b<0){
        b=-b; y1=-y1; y2=-y2; swap(y1,y2);
    }
    if(a==0)
    {
        if(b==0)
        {
            if(c==0)
            {
                printf("%lld\n", (y2-y1+1)*(x2-x1+1));
            }
            else
                printf("0\n");
        }
        else
        {
            if(y1<=c/b && c/b>=y2) printf("%lld\n", x2-x1+1);
            else printf("0\n");
        }
    }
    else
    {
        if(b==0)
        {
            if(y1<=c/a && c/a>=y2) printf("%lld\n", y2-y1+1);
            else printf("0\n");
        }
        else
        {
            ll x, y;
            int g=exgcd(a, b, x, y);
            if(c%g) printf("0\n");
            else
            {
                //cout<<123<<endl;
                x*=(c/g); y*=(c/g);
                b/=g;   a/=g;
                ll al=ceil(x1-x, b);
                ll ar=floor(x2-x, b);
                ll bl=ceil(y-y2, a);
                ll br=floor(y-y1, a);
                printf("%lld\n", max(0LL, min(br, ar)-max(bl, al)+1));
            }
        }
    }
}